#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "stack"

using namespace std;
/*HJJ QQ479287006
 *输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//TODO 抄的 不知道会不会背
int trap(vector<int> &height) {

    int low = 0;
    int high = height.size() - 1;

    int ret = 0;
    int leftMax = 0;
    int rightMax = 0;
    while (low < high) {

        leftMax = max(leftMax, height[low]);
        rightMax = max(rightMax, height[high]);

        if (height[low] < height[high]) {

            ret += leftMax - height[low++];

        } else {

            ret += rightMax - height[high--];
        }

    }

    return ret;

}
//todo 单调站尝试

int trap(vector<int> &height) {
    stack<int> st;
    // 元素是递增还是递减 栈里面 这个应该是递减的 大于他就形成低洼处了
    int ret = 0;
    for (int i = 0; i < height.size(); ++i) {
        if (st.empty()) {
            st.push(i);
        } else {
            while (!st.empty() && height[i] > height[st.top()]) {
                int temp = st.top();//计算出一个当前的index作为备份
                st.pop();
                if (st.empty())
                    break;//没有左边墙不能存水
                int left = st.top();
                int right = i;
                int h = height[temp];
                ret += (right - left - 1) * (min(height[left], height[right]) - h);
            }
            st.push(i);
        }
    }

    return ret;

}